package com.algorithm.offer.linkedtable;

import com.sun.jmx.snmp.SnmpNull;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @Author: huangzhigao
 * @Date: 2021/11/8 22:13
 * 两个链表的第一个公共结点
 * <p>
 * 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的
 */
public class JZ52 {
    public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        //双指针，两个同时走，如果在遍历各自的链表时，如果在相遇时，则为第一个公共点，遍历完自己的，在去遍历他人的，总长度为m+n,期间相遇则有公共点，否则将同时为null
        while (l1 != l2) {
            l1 = l1 == null ? pHead2 : l1.next;
            l2 = l2 == null ? pHead1 : l2.next;
        }
        return l1;
    }

}
